class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0
        for i in range(1, n):
            buy1 = max(buy1, -prices[i])# 买一
            sell1 = max(sell1, buy1 + prices[i])# 卖一
            buy2 = max(buy2, sell1 - prices[i]) # 买二
            sell2 = max(sell2, buy2 + prices[i])# 卖二
        return sell2
'''
错误答案prices = [1,2,4,2,5,7,2,4,9,0]
dp:
[0, 1, 3, 0, 3, 5, 0, 2, 7, 0]
[0, 0, 0, 0, 1, 2, 3, 3, 5, 7]
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        dp = [0] * n
        minprice = prices[0]
        # 正序
        def isFront(prices):
            for i in range(1,n):
                if prices[i] < prices[i - 1]:
                    return False
            return True
        # 逆序
        def isBack(prices):
            for i in range(1, n):
                if prices[i] >= prices[i - 1]:
                    return False
            return True
        if isFront(prices):
            return prices[n - 1] - prices[0]
        if isBack(prices):
            return 0
        # 一般情况    
        for i in range(1, n):
            if prices[i] < prices[i - 1]:
                minprice = prices[i]
            #print(minprice)
            dp[i] = prices[i] - minprice
        dp = sorted(dp)
        return dp[-1] + dp[-2]
'''